import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

class Solution {
    public List<Integer> findSubstring(String s, String[] words) {
        List<Integer> list = new ArrayList<>();
        int lenWords = words.length;
        int lenWord = words[0].length();
        int totalLength = lenWord * lenWords;
        if(s.length() < totalLength){
            return list;
        }
        int left = 0;
        int right = 0;
        Map<String, Integer> mapWords = new HashMap<>();
        Map<String, Integer> mapSS = new HashMap<>();
        //先把数组中的字符串放到Hash表中
        for(String str : words){
            int value = mapWords.getOrDefault(str, 0);
            mapWords.put(str, value + 1);
        }
        StringBuilder sb = new StringBuilder();
        while(right < s.length()){
            //进窗口
            char ch = s.charAt(right);
            sb.append(ch);
            //出窗口
            if(right - left + 1 > totalLength){
                sb.deleteCharAt(0);
                left++;
            }
            //进集合
            if(sb.toString().length() == totalLength){
                Map<String, Integer> mapS = new HashMap<>();
                for(int i = 0; i < totalLength; i+=lenWord){
                    StringBuilder stringBuilder = new StringBuilder();
                    for(int j = i; j < i + lenWord; j++){
                        stringBuilder.append(sb.charAt(j));
                    }
                    int val = mapS.getOrDefault(stringBuilder.toString(), 0);
                    mapS.put(stringBuilder.toString(), val + 1);
                }
                mapSS = mapS;
            }
            //更新结果
            if(isSame(mapSS, mapWords)){
                list.add(left);
            }
            right++;
        }
        return list;
    }
    private boolean isSame(Map<String, Integer> mapS, Map<String, Integer> mapWords){
        for(Map.Entry<String, Integer> entry : mapWords.entrySet()){
            String key = entry.getKey();
            int value = entry.getValue();
            if(!mapS.containsKey(key) || mapS.get(key) != value){
                return false;
            }
        }
        return true;
    }

    public List<Integer> findSubstring1(String s, String[] words) {
        List<Integer> list = new ArrayList<>();
        //如果s没有words的总长度长，就不需要执行下面的逻辑判断了
        if(s.length() < words.length * words[0].length()){
            return list;
        }
        //采用滑动窗口的办法解决
        int lenS = s.length();
        int lenWord = words[0].length();
        int num = words.length;
        int lenWords = lenWord * num;
        int left = 0;
        int right = 0;
        //定义哈希表
        Map<String, Integer> mapWords = new HashMap<>();
        //把words里面的字符串都放进哈希表中
        for(String word : words){
            mapWords.put(word, mapWords.getOrDefault(word, 0) + 1);
        }
        Map<String, Integer> mapS = new HashMap<>();
        int count = 0;
        while(right + lenWords <= lenS){
            //进窗口 + 维护有效字符串
            for(int i = 1; i <= num; i++){
                String key = s.substring(right + lenWord * (i - 1), right + lenWord * i);
                mapS.put(key, mapS.getOrDefault(key, 0) + 1);
                if(mapS.get(key) <= mapWords.getOrDefault(key, 0)){
                    count++;
                }
            }
            //出窗口 + 维护有效字符串
            if(right - left > 0){
                for(int i = 1; i <= num; i++){
                    String key = s.substring(left + lenWord * (i - 1), left + lenWord * i);
                    int value = mapS.get(key);
                    if(value <= mapWords.getOrDefault(key, 0)){
                        count--;
                    }
                    if(value > 1){
                        mapS.put(key, value - 1);
                    }else{
                        mapS.remove(key);
                    }
                }
                left++;
            }
            //更新结果
            if(count == num){
                list.add(left);
            }
            right++;
        }
        return list;
    }

    public List<Integer> findSubstring2(String s, String[] words) {
        List<Integer> list = new ArrayList<>();
        //如果s没有words的总长度长，就不需要执行下面的逻辑判断了
        if(s.length() < words.length * words[0].length()){
            return list;
        }
        //采用滑动窗口的办法解决
        int lenS = s.length();
        int lenWord = words[0].length();
        int num = words.length;
        int lenWords = lenWord * num;
        //定义哈希表
        Map<String, Integer> mapWords = new HashMap<>();
        //把words里面的字符串都放进哈希表中
        for(String word : words){
            mapWords.put(word, mapWords.getOrDefault(word, 0) + 1);
        }
        for(int i = 0; i < lenWord; i++){
            Map<String, Integer> mapS = new HashMap<>();
            int count = 0;
            int left = i;
            int right = i;
            while(right + lenWord <= lenS){
                //进窗口 + 维护有效字符串
                String keyRight = s.substring(right, right + lenWord);
                mapS.put(keyRight, mapS.getOrDefault(keyRight, 0) + 1);
                if(mapS.get(keyRight) <= mapWords.getOrDefault(keyRight, 0)){
                    count++;
                }
                //出窗口 + 维护有效字符串
                if(right - left + 1> lenWords){
                    String keyLeft = s.substring(left, left + lenWord);
                    int value = mapS.get(keyLeft);
                    if(value <= mapWords.getOrDefault(keyLeft, 0)){
                        count--;
                    }
                    if(value > 1){
                        mapS.put(keyLeft, value - 1);
                    }else{
                        mapS.remove(keyLeft);
                    }
                    left+=lenWord;
                }
                //更新结果
                if(count == num){
                    list.add(left);
                }
                right+=lenWord;
            }
        }

        return list;
    }
}